﻿// 7-1 列出连通集 (25分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
user:Lidongcheng
date:20191212 1:00pm - 7:00 pm
key:1.dfs简单一点，但是坑很多，做递归函数若是想参数中的容器想保持不变就要引用。
	2.做完bfs都忘了，太复杂了。
*/

#include <iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<set>
#include<stack>
using namespace std;
int find(vector<int>* a, vector<int> b,int n) //通过比较内容，返回第一个查找到的b二级动态所在一级动态a中下标
{

	for (int i = 0; i < n; i++)
	{
		if (b == a[i])

		{
			return i;
		}
	}
	return 0;
}
//DFS函数，参数依次是，一级动态数组，二级动态数组，外部引用set类型容器，迭代器（可能可以放在里面),标记栈用于保存每一次的迭代器取得的一级数组中未访问元素）
int DFS(vector<int>* a, vector<int> b,  set<int> &s,int n, vector<int>::iterator it,stack<int>&dfs_stack)
{	
	int g =dfs_stack.top();
	dfs_stack.pop();
	if (!s.count(g)) 
	{
		cout << " "<<g;
		if (s.size() <= n)
		{
			s.insert(g);
		}
		for (it = b.begin(); it != b.end(); it++)
		{
			if (!s.count(*it))
			{
				dfs_stack.push(*it);
				DFS(a, a[*it], s, n,it,dfs_stack);
			}
		}
	}
	else{
		return 0;
	}
}

int main()
{

	int n, e,i,j;
	cin >> n >> e;

	int* c = new int[2*e];//用来键值

	for (i = 0; i < 2 * e; i++)
	{//将题目每一个键值保存进去了
		cin >> c[i];
	}

	int* b= new int [n];//用来存顶点状态

	for (i = 0; i < n; i++)
	{//将题目每一个顶点状态存为0，即未找c到之前的状态；
		 b[i]=0;
	}


	vector<int>*a=new vector<int>[n];//用来存顶点

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < 2*e;j++)
		{
			if (i == c[j]) //若在键值对记录中搜索到与i相等的
			{
				b[i] = 1;//有一次相等我们就认为这个点不是孤立点
				if (j % 2)//若j是奇数
				{
					a[i].push_back(c[j-1]);//读它左边的
				}
				else 
				{
					a[i].push_back(c[j+1]);//读它右边的
				}
			}
		
		}
		sort(a[i].begin(), a[i].end());
	}
	
	/*
	vector<int>::iterator it;
	测试输出
	for (i = 0; i < n; i++)
	{
		if (a[i].empty())
		{
			cout << i << endl;
		}
		else
		{
			for (it = a[i].begin(); it != a[i].end(); it++)

			{
				cout << *it << " ";
			}
			cout << "\n";
		}
	}
  */

	vector<int>::iterator it;

	//开始深度搜索
	set<int>dfs;
	stack<int> dfs_stack;//这个栈是为了解决find函数找到相同的只能返回第一个的情况

	for (i = 0; i < n; i++)//一个节点一个节点的尝试作为队列头
	{
		if (!dfs.count(i)) //此顶点未被查找过(由于上一次查询是0或1，这一次我们在查询之后将其置为-1)
		{
			cout << "{";
			dfs_stack.push(i);
			DFS(a, a[i], dfs, n, it, dfs_stack);
			cout << " }"<<"\n";
		}
	}
	
	//开始广度搜索
	queue<vector<int>> d;//用个队列来广度搜索顶点
	set<int>BFS;
	for (i = 0; i < n; i++)//一个节点一个节点的尝试作为队列头
	{
		if (b[i] != -1&& !BFS.count(i)) //此顶点未被查找过(由于上一次查询是0或1，这一次我们在查询之后将其置为-1)
		{
			cout << "{ ";
			d.push(a[i]);//首节点放入队头
			cout << i << " ";
			while (!d.empty())
			{
				if (d.front().empty() != 1 )//队列头存的这个节点有东西,对头有东西且未被访问过
				{
					b[i] = -1;//本轮的i要马上打上标记
					for (it = d.front().begin(); it != d.front().end(); it++)
						//*it表示了里面的每一个整数
					{
						if (b[*it] != -1) {
							if (!BFS.count(*it))//已输出集合找不到它
							{
								cout << *it << " ";
								BFS.insert(*it);
							}
							d.push(a[*it]);
						}	
					}
					b[find(a, d.front(), n)] = -1;//内容被访问过置为-1			
					d.pop();
				}
				else //此时访问到了一个被标记点
				{	
					d.pop();
				}
				
			}
			
		}
		else
		{
			if (!BFS.count(i))//已输出集合找不到它
			{
				cout << "{";
				cout << i<< " ";
				BFS.insert(i);
			}
			continue;
		}
		cout << "}" << endl;
	}
	

}


